# Chinese remainder theorem and Euler totient function.
Now and then I am reminded of the Chinese remainder theorem. This time as finding a nice explicit bijection for the multiplicative property of the Euler totient function $\phi$, where $\phi(mn) = \phi(m) \phi(n)$ if $\gcd(m,n) = 1$. Well, let us start with the remainder theorem, what does it say?
Denote $Z_{m}= \set{0,1,...,m-1}$ to be the integer ring modulo $m$. The remainder theorem states, if $\gcd(m,n)=1$, then $$
Z_{mn} \simeq Z_{m} \times Z_{n}
$$via the isomorphism $$
x \bmod{mn} \mapsto (x \bmod{m},x \bmod{n}).
$$
What is the intuition behind this? We start with some explorations.
## The bijection.
The ring isomorphism is both a ring homomorphism and a bijection. Let us establish the bijection, which has a nice diagrammatic interpretation.
Let us fix positive integers $m$ and $n$ where $\gcd(m,n) =1$.
In the integer ring modulo $m$, $Z_{m}$, and starting from $0$. If we keep incrementing by one, we wrap back to $0$ when we increased to $m$. Similarly in $Z_{n}$. Since $x = 1 + \cdots + 1$, a repeated sum of $x$ times, we see the mapping above is suggesting that $$
1 + \cdots+ 1 \bmod mn \mapsto(1+\cdots +1 \bmod m, 1+\cdots +1 \bmod n).
$$
Now, let us draw a table, where the columns and rows are labeled by $Z_{m}$ and $Z_{n}$ respectively. The remainder theorem claims the mapping is a bijection means *starting at $(0,0)$, we can fill the table fully by going in the (1,1) direction, and wrapping around as needed!*
For example, let us take $m = 4$ and $n = 9$. For each $x$, the coordinate of $x$ can be found at $(x \bmod m, x \bmod n)$, so we have the following labeling: $$
\begin{array}{c|c|c|c|c}
& 0 & 1 & 2 & 3 \\ \hline
0 & 0 & 9 & & \\ \hline
1 & & 1 & {\tiny \searrow} & \\ \hline
2 & & & 2 & \\ \hline
3 & & & & 3 \\ \hline
4 & 4 & & & \\ \hline
5 & & 5 & & \\ \hline
6 & & & 6 & \\ \hline
7 & & & & 7 \\ \hline
8 & 8 & & &
\end{array}
$$
Notice how we fill diagonally (in the $\searrow$ southeast direction) and wraps around as needed. Remainder theorem ensures this will fill it completely from 0 to 35: $$
\begin{array}{c|c|c|c|c}
& 0 & 1 & 2 & 3 \\ \hline
0 & 0 & 9 &18 &27 \\ \hline
1 &28 & 1 &10 &19 \\ \hline
2 &20 &29 & 2 &11 \\ \hline
3 &12 &21 &30 & 3 \\ \hline
4 & 4 &13 &22 &31 \\ \hline
5 &32 & 5 &14 &23 \\ \hline
6 &24 &33 & 6 &15 \\ \hline
7 &16 &25 &34 & 7 \\ \hline
8 & 8 &17 &26 &35
\end{array}
$$
As for a non-example. Consider $m = 4$ and $n = 6$, which are not coprime. Then the proposed mapping will not fill the diagram and gives collisions: $$
\begin{array}{c|c|c|c|c}
& 0 & 1 & 2 & 3 \\ \hline
0 & 0 & & 6 & \\ \hline
1 & & 1 & & 7 \\ \hline
2 & 8 & & 2 & \\ \hline
3 & & 9 & & 3 \\ \hline
4 & 4 & &10 & \\ \hline
5 & & 5 & &11
\end{array}
$$where we see $12$ will be filled at the $(0,0)$ spot! The mapping is therefore not injective nor surjective in this case.
## Multiplicativity of Euler's totient function.
Above further gives a nice diagram of the multiplicative property of Euler's totient function $\phi$.
Denote $\phi(n)$ to be the number of positive integers from $1$ to $n$ that is coprime with $n$. We have multiplicative property where if $\gcd(m,n) = 1$, then $$
\phi(mn) = \phi(m)\phi(n).
$$
The diagram and the mapping above from the remainder theorem gives a nice visualization of this. Denote $\Phi(n)$ to be the set of positive integers from $1$ to $n$ that are coprime with $n$. If we highlight the elements in $\Phi(m)$ and $\Phi(n)$ in the row and column heading, then the corresponding elements in the table are precisely the elements of $\Phi(mn)$!
For example, $\Phi(4) = \set{1,3}$ and $\Phi(9) =\set{1,2,4,5,7,8}$. We also have $\Phi(36) = \set{1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35}$. Now observe the diagram with those elements highlighted: $$
\begin{array}{c|c|c|c|c}
& 0 & \color{blue}1 & 2 & \color{blue} 3 \\ \hline
0 & 0 & 9 &18 &27 \\ \hline
\color{blue}1 &28 & \color{blue}1 &10 &\color{blue}19 \\ \hline
\color{blue}2 &20 &\color{blue}29 & 2 &\color{blue}11 \\ \hline
3 &12 &21 &30 & 3 \\ \hline
\color{blue}4 & 4 &\color{blue}13 &22 &\color{blue}31 \\ \hline
\color{blue}5 &32 &\color{blue} 5 &14 &\color{blue}23 \\ \hline
6 &24 &33 & 6 &15 \\ \hline
\color{blue}7 &16 &\color{blue}25 &34 &\color{blue} 7 \\ \hline
\color{blue}8 & 8 &\color{blue}17 &26 &\color{blue}35
\end{array}
$$
Whence we have bijection between $\Phi(mn)$ and $\Phi(m) \times \Phi(n)$ by the same mapping $x \mapsto (x \bmod m, x \bmod n)$ as well!
One way to prove these is to exploit Bezout's lemma and properties of primes and prime factorization.